home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_419 / yacc / src.lzh / Src / RCS / mkpar.c,v < prev    next >
Text File  |  1990-07-14  |  7KB  |  397 lines
  1. head     1.1;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.1
  10. date     90.07.14.18.54.52;  author loftus;  state Exp;
  11. branches ;
  12. next     ;
  13.  
  14.  
  15. desc
  16. @@
  17.  
  18.  
  19.  
  20. 1.1
  21. log
  22. @Initial revision
  23. @
  24. text
  25. @#include "defs.h"
  26.  
  27. action **parser;
  28. int SRtotal;
  29. int RRtotal;
  30. short *SRconflicts;
  31. short *RRconflicts;
  32. short *defred;
  33. short *rules_used;
  34. short nunused;
  35. short final_state;
  36.  
  37. static int SRcount;
  38. static int RRcount;
  39.  
  40. extern action *parse_actions();
  41. extern action *get_shifts();
  42. extern action *add_reductions();
  43. extern action *add_reduce();
  44.  
  45.  
  46. make_parser()
  47. {
  48.     register int i;
  49.  
  50.     parser = NEW2(nstates, action *);
  51.     for (i = 0; i < nstates; i++)
  52.     parser[i] = parse_actions(i);
  53.  
  54.     find_final_state();
  55.     remove_conflicts();
  56.     unused_rules();
  57.     if (SRtotal + RRtotal > 0) total_conflicts();
  58.     defreds();
  59. }
  60.  
  61.  
  62. action *
  63. parse_actions(stateno)
  64. register int stateno;
  65. {
  66.     register action *actions;
  67.  
  68.     actions = get_shifts(stateno);
  69.     actions = add_reductions(stateno, actions);
  70.     return (actions);
  71. }
  72.  
  73.  
  74. action *
  75. get_shifts(stateno)
  76. int stateno;
  77. {
  78.     register action *actions, *temp;
  79.     register shifts *sp;
  80.     register short *to_state;
  81.     register int i, k;
  82.     register int symbol;
  83.  
  84.     actions = 0;
  85.     sp = shift_table[stateno];
  86.     if (sp)
  87.     {
  88.     to_state = sp->shift;
  89.     for (i = sp->nshifts - 1; i >= 0; i--)
  90.     {
  91.         k = to_state[i];
  92.         symbol = accessing_symbol[k];
  93.         if (ISTOKEN(symbol))
  94.         {
  95.         temp = NEW(action);
  96.         temp->next = actions;
  97.         temp->symbol = symbol;
  98.         temp->number = k;
  99.         temp->prec = symbol_prec[symbol];
  100.         temp->action_code = SHIFT;
  101.         temp->assoc = symbol_assoc[symbol];
  102.         actions = temp;
  103.         }
  104.     }
  105.     }
  106.     return (actions);
  107. }
  108.  
  109. action *
  110. add_reductions(stateno, actions)
  111. int stateno;
  112. register action *actions;
  113. {
  114.     register int i, j, m, n;
  115.     register int ruleno, tokensetsize;
  116.     register unsigned *rowp;
  117.  
  118.     tokensetsize = WORDSIZE(ntokens);
  119.     m = lookaheads[stateno];
  120.     n = lookaheads[stateno + 1];
  121.     for (i = m; i < n; i++)
  122.     {
  123.     ruleno = LAruleno[i];
  124.     rowp = LA + i * tokensetsize;
  125.     for (j = ntokens - 1; j >= 0; j--)
  126.     {
  127.         if (BIT(rowp, j))
  128.         actions = add_reduce(actions, ruleno, j);
  129.     }
  130.     }
  131.     return (actions);
  132. }
  133.  
  134.  
  135. action *
  136. add_reduce(actions, ruleno, symbol)
  137. register action *actions;
  138. register int ruleno, symbol;
  139. {
  140.     register action *temp, *prev, *next;
  141.  
  142.     prev = 0;
  143.     for (next = actions; next && next->symbol < symbol; next = next->next)
  144.     prev = next;
  145.  
  146.     while (next && next->symbol == symbol && next->action_code == SHIFT)
  147.     {
  148.     prev = next;
  149.     next = next->next;
  150.     }
  151.  
  152.     while (next && next->symbol == symbol &&
  153.         next->action_code == REDUCE && next->number < ruleno)
  154.     {
  155.     prev = next;
  156.     next = next->next;
  157.     }
  158.  
  159.     temp = NEW(action);
  160.     temp->next = next;
  161.     temp->symbol = symbol;
  162.     temp->number = ruleno;
  163.     temp->prec = rprec[ruleno];
  164.     temp->action_code = REDUCE;
  165.     temp->assoc = rassoc[ruleno];
  166.  
  167.     if (prev)
  168.     prev->next = temp;
  169.     else
  170.     actions = temp;
  171.  
  172.     return (actions);
  173. }
  174.  
  175.  
  176. find_final_state()
  177. {
  178.     register int goal, i;
  179.     register short *to_state;
  180.     register shifts *p;
  181.  
  182.     p = shift_table[0];
  183.     to_state = p->shift;
  184.     goal = ritem[1];
  185.     for (i = p->nshifts - 1; i >= 0; --i)
  186.     {
  187.     final_state = to_state[i];
  188.     if (accessing_symbol[final_state] == goal) break;
  189.     }
  190. }
  191.  
  192.  
  193. unused_rules()
  194. {
  195.     register int i;
  196.     register action *p;
  197.  
  198.     rules_used = (short *) MALLOC(nrules*sizeof(short));
  199.     if (rules_used == 0) no_space();
  200.  
  201.     for (i = 0; i < nrules; ++i)
  202.     rules_used[i] = 0;
  203.  
  204.     for (i = 0; i < nstates; ++i)
  205.     {
  206.     for (p = parser[i]; p; p = p->next)
  207.     {
  208.         if (p->action_code == REDUCE && p->suppressed == 0)
  209.         rules_used[p->number] = 1;
  210.     }
  211.     }
  212.  
  213.     nunused = 0;
  214.     for (i = 3; i < nrules; ++i)
  215.     if (!rules_used[i]) ++nunused;
  216.  
  217.     if (nunused)
  218.     if (nunused == 1)
  219.         fprintf(stderr, "%s: 1 rule never reduced\n", myname);
  220.     else
  221.         fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
  222. }
  223.  
  224.  
  225. remove_conflicts()
  226. {
  227.     register int i;
  228.     register int symbol;
  229.     register action *p, *q;
  230.  
  231.     SRtotal = 0;
  232.     RRtotal = 0;
  233.     SRconflicts = NEW2(nstates, short);
  234.     RRconflicts = NEW2(nstates, short);
  235.     for (i = 0; i < nstates; i++)
  236.     {
  237.     SRcount = 0;
  238.     RRcount = 0;
  239.     for (p = parser[i]; p; p = q->next)
  240.     {
  241.         symbol = p->symbol;
  242.         q = p;
  243.         while (q->next && q->next->symbol == symbol)
  244.         q = q->next;
  245.         if (i == final_state && symbol == 0)
  246.         end_conflicts(p, q);
  247.         else if (p != q)
  248.         resolve_conflicts(p, q);
  249.     }
  250.     SRtotal += SRcount;
  251.     RRtotal += RRcount;
  252.     SRconflicts[i] = SRcount;
  253.     RRconflicts[i] = RRcount;
  254.     }
  255. }
  256.  
  257.  
  258. end_conflicts(p, q)
  259. register action *p, *q;
  260. {
  261.     for (;;)
  262.     {
  263.     SRcount++;
  264.     p->suppressed = 1;
  265.     if (p == q) break;
  266.     p = p->next;
  267.     }
  268. }
  269.  
  270.  
  271. resolve_conflicts(first, last)
  272. register action *first, *last;
  273. {
  274.     register action *p;
  275.     register int count;
  276.  
  277.     count = 1;
  278.     for (p = first; p != last; p = p->next)
  279.      ++count;
  280.     assert(count > 1);
  281.  
  282.     if (first->action_code == SHIFT && count == 2 &&
  283.         first->prec > 0 && last->prec > 0)
  284.     {
  285.     if (first->prec == last->prec)
  286.     {
  287.         if (first->assoc == LEFT)
  288.         first->suppressed = 2;
  289.         else if (first->assoc == RIGHT)
  290.         last->suppressed = 2;
  291.         else
  292.         {
  293.         first->suppressed = 2;
  294.         last->suppressed = 2;
  295.         first->action_code = ERROR;
  296.         last->action_code = ERROR;
  297.         }
  298.     }
  299.     else if (first->prec < last->prec)
  300.         first->suppressed = 2;
  301.     else
  302.         last->suppressed = 2;
  303.     }
  304.     else
  305.     {
  306.     if (first->action_code == SHIFT)
  307.         SRcount += (count - 1);
  308.         else
  309.         RRcount += (count - 1);
  310.     for (p = first; p != last; p = p->next, p->suppressed = 1)
  311.         continue;
  312.     }
  313. }
  314.  
  315.  
  316. total_conflicts()
  317. {
  318.     fprintf(stderr, "%s: ", myname);
  319.     if (SRtotal == 1)
  320.     fprintf(stderr, "1 shift/reduce conflict");
  321.     else if (SRtotal > 1)
  322.     fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
  323.  
  324.     if (SRtotal && RRtotal)
  325.     fprintf(stderr, ", ");
  326.  
  327.     if (RRtotal == 1)
  328.     fprintf(stderr, "1 reduce/reduce conflict");
  329.     else if (RRtotal > 1)
  330.     fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
  331.  
  332.     fprintf(stderr, ".\n");
  333. }
  334.  
  335.  
  336. int
  337. sole_reduction(stateno)
  338. int stateno;
  339. {
  340.     register int count, ruleno;
  341.     register action *p;
  342.  
  343.     count = 0;
  344.     ruleno = 0; 
  345.     for (p = parser[stateno]; p; p = p->next)
  346.     {
  347.     if (p->action_code == SHIFT && p->suppressed == 0)
  348.         return (0);
  349.     else if (p->action_code == REDUCE && p->suppressed == 0)
  350.     {
  351.         if (ruleno > 0 && p->number != ruleno)
  352.         return (0);
  353.         if (p->symbol != 1)
  354.         ++count;
  355.         ruleno = p->number;
  356.     }
  357.     }
  358.  
  359.     if (count == 0)
  360.     return (0);
  361.     return (ruleno);
  362. }
  363.  
  364.  
  365. defreds()
  366. {
  367.     register int i;
  368.  
  369.     defred = NEW2(nstates, short);
  370.     for (i = 0; i < nstates; i++)
  371.     defred[i] = sole_reduction(i);
  372. }
  373.  
  374. free_action_row(p)
  375. register action *p;
  376. {
  377.   register action *q;
  378.  
  379.   while (p)
  380.     {
  381.       q = p->next;
  382.       FREE(p);
  383.       p = q;
  384.     }
  385. }
  386.  
  387. free_parser()
  388. {
  389.   register int i;
  390.  
  391.   for (i = 0; i < nstates; i++)
  392.     free_action_row(parser[i]);
  393.  
  394.   FREE(parser);
  395. }
  396. @
  397.